#include <bits/stdc++.h>
#include <cassert>
using namespace std;

vector<int> lds(vector<int> n) {
    sort(n.begin(), n.end());

    int max = 0;
    vector<int> dp(n.size(), 1), w(n.size(), -1);

    for (int i=0; i < n.size(); i++){
        for (int j = 0; j < i; j++)
            if (n[i] % n[j] == 0 && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                w[i] = j;
            }
        if (dp[i] > dp[max]) max = i;
    }
    vector<int> ans;
    for (int i = max; i != -1; i = w[i]) ans.push_back(n[i]);
    reverse(ans.begin(), ans.end());
    return ans;
}

int main() {
    vector<int> a = {1, 4, 8, 16}, b = {2, 4, 8}, c = {3, 9, 18};
    assert(lds({1, 16, 7, 8, 4}) == a);
    assert(lds({2, 4, 3, 8}) == b);
    assert(lds({3, 4, 9, 16, 18}) == c);
}
